//给定一个整数数组，它表示BST(即 二叉搜索树 )的 先序遍历 ，构造树并返回其根。 
//
// 保证 对于给定的测试用例，总是有可能找到具有给定需求的二叉搜索树。 
//
// 二叉搜索树 是一棵二叉树，其中每个节点， Node.left 的任何后代的值 严格小于 Node.val , Node.right 的任何后代的值 严格大
//于 Node.val。 
//
// 二叉树的 前序遍历 首先显示节点的值，然后遍历Node.left，最后遍历Node.right。 
//
// 
//
// 示例 1： 
//
// 
//
// 
//输入：preorder = [8,5,1,7,10,12]
//输出：[8,5,10,1,7,null,12]
// 
//
// 示例 2: 
//
// 
//输入: preorder = [1,3]
//输出: [1,null,3]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= preorder.length <= 100 
// 1 <= preorder[i] <= 10^8 
// preorder 中的值 互不相同 
// 
//
// 
//
// Related Topics 栈 树 二叉搜索树 数组 二叉树 单调栈 👍 317 👎 0


//leetcode submit region begin(Prohibit modification and deletion)



/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode bstFromPreorder(int[] preorder) {

//        TreeNode root = new TreeNode(preorder[0]);
//        for (int i = 1; i < preorder.length; i++) {
//            insert(root, preorder[i]);
//        }
//        return root;

//        //上限法
//        return insert2(preorder, Integer.MAX_VALUE);
        //分治法
        return partition(preorder, 0, preorder.length-1);
    }
//    private TreeNode insert(TreeNode root, int val) {
//        if (root == null) {
//            return new TreeNode(val);
//        }
//        if(val < root.val) {
//            root.left = insert(root.left, val);
//        }else if(root.val < val){
//            root.right = insert(root.right, val);
//        }
//        return root;
//    }
//    int i = 0;
//    private TreeNode insert2(int[] preorder, int max){
//        if(i == preorder.length)
//            return null;
//        int val = preorder[i];
//        if(val > max){
//            return null;
//        }
//        TreeNode node = new TreeNode(val);
//        i++;
//        node.left = insert2(preorder, val);
//        node.right = insert2(preorder, max);
//        return node;
//    }
    private TreeNode partition(int[] preorder, int start, int end){
        if(start > end){
            return null;
        }
        TreeNode root = new TreeNode(preorder[start]);//根节点
        int i = start + 1;
        while(i <= end && preorder[i] < preorder[start]){
            i++;
        }
        //i为根节点的右子树区间的开始
        root.left = partition(preorder, start + 1, i - 1);
        root.right = partition(preorder, i, end);
        return root;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
